1. Field of the Invention
The present invention relates generally to location estimation systems and methods. More particularly, the present invention relates to estimating a location of a client device.
2. Description of Related Art
The approximate location of a client device within the coverage ranges of a set of WiFi access points can be estimated based on the existing information of the locations and ranges of the WiFi access points stored in a pre-computed database.
However, the information in the WiFi access points database may not be accurate due to various reasons. Often, the locations and coverage ranges of the access points in the database are only estimated values that do not accurately reflect the true location and range of the access point. The database may also contain invalid access points locations as access points were removed from the original location and the location data in the database is not updated timely.
Some location estimation systems adopt an iterative process to calculate the centroid of all the access points detected by the client device. To determine the accuracy of the estimated location, these systems compute the average of the estimated coverage range of all the access points used in the calculation. Then, if the accuracy is beyond a certain threshold, those access points that are furthest from the computed centroid are discarded and the system re-calculates the centroid and accuracy. If the accuracy is below the threshold, the computed centroid is designated as the location of the device and returned to the client device with the accuracy. If many access points have been removed from the calculation after many iterations, and the estimated accuracy is still over the acceptable threshold, the location estimation algorithm does not return a location to the client device.
The above computation to determine the centroid and the accuracy of the location to return largely depends on the average of the accuracy of the locations and ranges of the access points used in the computation. As such, the limitations of the above approach are evident when the locations and ranges in the database are inaccurate, due to, for example, either insufficient spatial samples or samples with large spatial noises collected in the past.
Usually there are two types of undesirable errors with the existing WiFi signal coverage. First, the centroid of the signal coverage may be biased towards the edge of the signal's true coverage due to insufficient and biased samples. Second, the coverage area of a signal may be overestimated if the GPS locations collected through the client device are inaccurate (e.g., with noises in the range of hundreds of meters or even kilometers), or decoupled from the current signal scan in time so the coverage data is stale. In addition, large spatial errors may occur if the client device is on the move.